/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode ans;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root.left == null && root.right == null) {
            return root;
        }
        ans = null;
        dfc(root,p,q);
        return ans;
    }

    public boolean dfc(TreeNode root,TreeNode p,TreeNode q) {
        if(root == null) {
            return false;
        }
        boolean lson = dfc(root.left, p, q);
        boolean rson = dfc(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            //lson && rson判断判,p.q是否存在,左右子树包含
            //root.val == p.val || root.val == q.val 防止p.q就是root节点
            ans = root;
        } 
        //如果满足一个条件，说明该子树存在p或q，返回true
        //如果满足上述的if条件，说明左有p或q，右有q或p
        return lson || rson || (root.val == p.val || root.val == q.val);
    }
}